Discrete Event Simulation
   HOME

TheInfoList



OR:

A discrete-event simulation (DES) models the operation of a
system A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. A system, surrounded and influenced by its environment (systems), environment, is described by its boundaries, ...
as a (
discrete Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory * Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit *Discrete group, a ...
)
sequence of events Time is the continued sequence of existence and events that occurs in an apparently irreversible succession from the past, through the present, into the future. It is a component quantity of various measurements used to sequence events, to ...
in time. Each event occurs at a particular instant in time and marks a change of
state State may refer to: Arts, entertainment, and media Literature * ''State Magazine'', a monthly magazine published by the U.S. Department of State * ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States * ''Our S ...
in the system. Between consecutive events, no change in the system is assumed to occur; thus the simulation time can directly jump to the occurrence time of the next event, which is called next-event time progression. In addition to next-event time progression, there is also an alternative approach, called incremental time progression, where time is broken up into small time slices and the system state is updated according to the set of events/activities happening in the time slice. Because not every time slice has to be simulated, a next-event time simulation can typically run faster than a corresponding incremental time simulation. Both forms of DES contrast with
continuous simulation Continuous Simulation refers to simulation approaches where a system is modeled with the help of variables that change continuously according to a set of differential equations. History It is notable as one of the first uses ever put to computers ...
in which the system state is changed continuously over time on the basis of a set of
differential equations In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, an ...
defining the rates of change of state variables.


Example

A common exercise in learning how to build discrete-event simulations is to model a
queue __NOTOC__ Queue () may refer to: * Queue area, or queue, a line or area where people wait for goods or services Arts, entertainment, and media *''ACM Queue'', a computer magazine * ''The Queue'' (Sorokin novel), a 1983 novel by Russian author ...
, such as customers arriving at a bank to be served by a teller. In this example, the system entities are Customer-queue and Tellers. The system events are Customer-Arrival and Customer-Departure. (The event of Teller-Begins-Service can be part of the logic of the arrival and departure events.) The system states, which are changed by these events, are Number-of-Customers-in-the-Queue (an integer from 0 to n) and Teller-Status (busy or idle). The
random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
s that need to be characterized to model this system
stochastic Stochastic (, ) refers to the property of being well described by a random probability distribution. Although stochasticity and randomness are distinct in that the former refers to a modeling approach and the latter refers to phenomena themselv ...
ally are Customer-Interarrival-Time and Teller-Service-Time. An agent-based framework for performance modeling of an optimistic parallel discrete event simulator is another example for a discrete event simulation.


Components

In addition to the logic of what happens when system events occur, discrete event simulations include the following: * Priority queue, * Animation event handler, and * Time re-normalization handler (as simulation runs, time variables lose precision. After a while all time variables should be re-normalized by subtracting the last processed event time).


State

A system state is a set of variables that captures the salient properties of the system to be studied. The state trajectory over time S(t) can be mathematically represented by a
step function In mathematics, a function on the real numbers is called a step function if it can be written as a finite linear combination of indicator functions of intervals. Informally speaking, a step function is a piecewise constant function having only ...
whose value can change whenever an event occurs.


Clock

The simulation must keep track of the current simulation time, in whatever measurement units are suitable for the system being modeled. In discrete-event simulations, as opposed to continuous simulations, time 'hops' because events are instantaneous – the clock skips to the next event start time as the simulation proceeds.


Events list

The simulation maintains at least one list of simulation events. This is sometimes called the ''pending event set'' because it lists events that are pending as a result of previously simulated event but have yet to be simulated themselves. An event is described by the time at which it occurs and a type, indicating the code that will be used to simulate that event. It is common for the event code to be parametrized, in which case, the event description also contains parameters to the event code. The event list is also referred to as the ''future event list'' (FEL) or ''future event set'' (FES). When events are instantaneous, activities that extend over time are modeled as sequences of events. Some simulation frameworks allow the time of an event to be specified as an interval, giving the start time and the end time of each event. Single-threaded simulation engines based on instantaneous events have just one current event. In contrast,
multi-threaded In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system. The implementation of threads and processes dif ...
simulation engines and simulation engines supporting an interval-based event model may have multiple current events. In both cases, there are significant problems with synchronization between current events. The pending event set is typically organized as a
priority queue In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...
, sorted by event time. That is, regardless of the order in which events are added to the event set, they are removed in strictly chronological order. Various priority queue implementations have been studied in the context of discrete event simulation; alternatives studied have included splay trees,
skip list In computer science, a skip list (or skiplist) is a probabilistic data structure that allows \mathcal(\log n) average complexity for search as well as \mathcal(\log n) average complexity for insertion within an ordered sequence of n elements. T ...
s,
calendar queue A calendar queue (CQ) is a priority queue (queue in which every element has associated priority and the dequeue operation removes the highest priority element). It is analogous to desk calendar, which is used by humans for ordering future events by ...
s, and ladder queues. On massively-parallel machines, such as
multi-core A multi-core processor is a microprocessor on a single integrated circuit with two or more separate processing units, called cores, each of which reads and executes program instructions. The instructions are ordinary CPU instructions (such a ...
or
many-core Manycore processors are special kinds of multi-core processors designed for a high degree of parallel processing, containing numerous simpler, independent processor cores (from a few tens of cores to thousands or more). Manycore processors are use ...
CPUs, the pending event set can be implemented by relying on non-blocking algorithms, in order to reduce the cost of synchronization among the concurrent threads. Typically, events are scheduled dynamically as the simulation proceeds. For example, in the bank example noted above, the event CUSTOMER-ARRIVAL at time t would, if the CUSTOMER_QUEUE was empty and TELLER was idle, include the creation of the subsequent event CUSTOMER-DEPARTURE to occur at time t+s, where s is a number generated from the SERVICE-TIME distribution.


Random-number generators

The simulation needs to generate
random variables A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
of various kinds, depending on the system model. This is accomplished by one or more
Pseudorandom number generator A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
s. The use of pseudo-random numbers as opposed to true random numbers is a benefit should a simulation need a rerun with exactly the same behavior. One of the problems with the random number distributions used in discrete-event simulation is that the steady-state distributions of event times may not be known in advance. As a result, the initial set of events placed into the pending event set will not have arrival times representative of the steady-state distribution. This problem is typically solved by bootstrapping the simulation model. Only a limited effort is made to assign realistic times to the initial set of pending events. These events, however, schedule additional events, and with time, the distribution of event times approaches its steady state. This is called ''bootstrapping'' the simulation model. In gathering statistics from the running model, it is important to either disregard events that occur before the steady state is reached or to run the simulation for long enough that the bootstrapping behavior is overwhelmed by steady-state behavior. (This use of the term ''bootstrapping'' can be contrasted with its use in both
statistics Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...
and
computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...
).


Statistics

The simulation typically keeps track of the system's
statistic A statistic (singular) or sample statistic is any quantity computed from values in a sample which is considered for a statistical purpose. Statistical purposes include estimating a population parameter, describing a sample, or evaluating a hypo ...
s, which quantify the aspects of interest. In the bank example, it is of interest to track the mean waiting times. In a simulation model, performance metrics are not analytically derived from
probability distributions In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon ...
, but rather as averages over replications, that is different runs of the model.
Confidence interval In frequentist statistics, a confidence interval (CI) is a range of estimates for an unknown parameter. A confidence interval is computed at a designated ''confidence level''; the 95% confidence level is most common, but other levels, such as 9 ...
s are usually constructed to help assess the quality of the output.


Ending condition

Because events are bootstrapped, theoretically a discrete-event simulation could run forever. So the simulation designer must decide when the simulation will end. Typical choices are "at time t" or "after processing n number of events" or, more generally, "when statistical measure X reaches the value x".


Three-Phased Approach

Pidd (1998) has proposed the three-phased approach to discrete event simulation. In this approach, the first phase is to jump to the next chronological event. The second phase is to execute all events that unconditionally occur at that time (these are called B-events). The third phase is to execute all events that conditionally occur at that time (these are called C-events). The three phase approach is a refinement of the event-based approach in which simultaneous events are ordered so as to make the most efficient use of computer resources. The three-phase approach is used by a number of commercial simulation software packages, but from the user's point of view, the specifics of the underlying simulation method are generally hidden.


Common uses


Diagnosing process issues

Simulation approaches are particularly well equipped to help users diagnose issues in complex environments. The theory of constraints illustrates the importance of understanding bottlenecks in a system. Identifying and removing bottlenecks allows improving processes and the overall system. For instance, in manufacturing enterprises bottlenecks may be created by excess inventory,
overproduction In economics, overproduction, oversupply, excess of supply or glut refers to excess of supply over demand of products being offered to the market. This leads to lower prices and/or unsold goods along with the possibility of unemployment. The de ...
, variability in processes and variability in routing or sequencing. By accurately documenting the system with the help of a simulation model it is possible to gain a bird’s eye view of the entire system. A working model of a system allows management to understand performance drivers. A simulation can be built to include any number of
performance indicator A performance indicator or key performance indicator (KPI) is a type of performance measurement. KPIs evaluate the success of an organization or of a particular activity (such as projects, programs, products and other initiatives) in which it en ...
s such as worker utilization, on-time delivery rate, scrap rate, cash cycles, and so on.


Hospital applications

An operating theater is generally shared between several surgical disciplines. Through better understanding the nature of these procedures it may be possible to increase the patient throughput. Example: If a heart surgery takes on average four hours, changing an operating room schedule from eight available hours to nine will not increase patient throughput. On the other hand, if a hernia procedure takes on average twenty minutes providing an extra hour may also not yield any increased throughput if the capacity and average time spent in the recovery room is not considered.


Lab test performance improvement ideas

Many systems improvement ideas are built on sound principles, proven methodologies (
Lean Lean, leaning or LEAN may refer to: Business practices * Lean thinking, a business methodology adopted in various fields ** Lean construction, an adaption of lean manufacturing principles to the design and construction process ** Lean governm ...
, Six Sigma, TQM, etc.) yet fail to improve the overall system. A simulation model allows the user to understand and test a performance improvement idea in the context of the overall system.


Evaluating capital investment decisions

Simulation modeling is commonly used to model potential investments. Through modeling investments decision-makers can make informed decisions and evaluate potential alternatives.


Network simulators

Discrete event simulation is used in computer network to simulate new protocols, different system architectures (distributed, hierarchical, centralised, P2P) before actual deployment. It is possible to define different evaluation metrics, such as service time, bandwidth, dropped packets, resource consumption, and so on.


See also

System modeling approaches: *
Finite-state machines A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
and
Markov chains A Markov chain or Markov process is a stochastic process, stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought ...
*
Stochastic process In probability theory and related fields, a stochastic () or random process is a mathematical object usually defined as a family of random variables. Stochastic processes are widely used as mathematical models of systems and phenomena that appea ...
and a special case,
Markov process A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
*
Queueing theory Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
and in particular birth–death process *
Discrete Event System Specification ''Devs'' is an American science fiction thriller television miniseries created, written, and directed by Alex Garland. It premiered on March 5, 2020, on FX on Hulu. Lily Chan (Sonoya Mizuno) is a software engineer for Amaya, a quantum computing ...
* Transaction-level modeling (TLM) Computational techniques: *
Computer experiment A computer experiment or simulation experiment is an experiment used to study a computer simulation, also referred to as an in silico system. This area includes computational physics, computational chemistry, computational biology and other similar ...
*
Computer simulation Computer simulation is the process of mathematical modelling, performed on a computer, which is designed to predict the behaviour of, or the outcome of, a real-world or physical system. The reliability of some mathematical models can be dete ...
*
Monte Carlo method Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be determi ...
*
Variance reduction In mathematics, more specifically in the theory of Monte Carlo methods, variance reduction is a procedure used to increase the precision of the estimates obtained for a given simulation or computational effort. Every output random variable fro ...
*
Pseudo-random number generator A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
Software: *
List of computer simulation software The following is a list of notable computer simulation software. Free or open-source * Advanced Simulation Library - open-source hardware accelerated multiphysics simulation software. * ASCEND - open-source equation-based modelling environment ...
*
List of discrete event simulation software This is a list of notable discrete-event simulation A discrete-event simulation (DES) models the operation of a system as a ( discrete) sequence of events in time. Each event occurs at a particular instant in time and marks a change of state in t ...
Disciplines: *
Industrial engineering Industrial engineering is an engineering profession that is concerned with the optimization of complex process (engineering), processes, systems, or organizations by developing, improving and implementing integrated systems of people, money, kno ...
*
Network simulation In computer network research, network simulation is a technique whereby a software program replicates the behavior of a real network. This is achieved by calculating the interactions between the different network entities such as routers, switche ...


References


Further reading

* * * * * * * * *{{cite book, title=Building software for simulation: theory and algorithms, with applications in C++, author=James J. Nutaro, publisher=Wiley, year=2010 Stochastic simulation Events (computing)